{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Bisect Squares LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #geometry #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #几何 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: cutSquares"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #平分正方形"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定两个正方形及一个二维平面。请找出将这两个正方形分割成两半的一条直线。假设正方形顶边和底边与 x 轴平行。</p>\n",
    "\n",
    "<p>每个正方形的数据<code>square</code>包含3个数值，正方形的左下顶点坐标<code>[X,Y] = [square[0],square[1]]</code>，以及正方形的边长<code>square[2]</code>。所求直线穿过两个正方形会形成4个交点，请返回4个交点形成线段的两端点坐标（两个端点即为4个交点中距离最远的2个点，这2个点所连成的线段一定会穿过另外2个交点）。2个端点坐标<code>[X<sub>1</sub>,Y<sub>1</sub>]</code>和<code>[X<sub>2</sub>,Y<sub>2</sub>]</code>的返回格式为<code>{X<sub>1</sub>,Y<sub>1</sub>,X<sub>2</sub>,Y<sub>2</sub>}</code>，要求若<code>X<sub>1</sub> != X<sub>2</sub></code>，需保证<code>X<sub>1</sub> &lt; X<sub>2</sub></code>，否则需保证<code>Y<sub>1</sub> &lt;= Y<sub>2</sub></code>。</p>\n",
    "\n",
    "<p>若同时有多条直线满足要求，则选择斜率最大的一条计算并返回（与Y轴平行的直线视为斜率无穷大）。</p>\n",
    "\n",
    "<p><strong>示例：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>\n",
    "square1 = {-1, -1, 2}\n",
    "square2 = {0, -1, 2}\n",
    "<strong>输出：</strong> {-1,0,2,0}\n",
    "<strong>解释：</strong> 直线 y = 0 能将两个正方形同时分为等面积的两部分，返回的两线段端点为[-1,0]和[2,0]\n",
    "</pre>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>square.length == 3</code></li>\n",
    "\t<li><code>square[2] &gt; 0</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [bisect-squares-lcci](https://leetcode.cn/problems/bisect-squares-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [bisect-squares-lcci](https://leetcode.cn/problems/bisect-squares-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[-1,1,3]\\n[0,0,5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cutSquares(self, square1: List[int], square2: List[int]) -> List[float]:\n",
    "        getCenter=lambda x,y,r:[x+r/2,y+r/2]\n",
    "        getAbc=lambda x1,y1,x2,y2:[y2-y1,x1-x2,y1*x2-y2*x1] if [x1,y1]!=[x2,y2] else [1,0,-x1]\n",
    "        crossY=lambda x:(x,-(a*x+c)/b) if b else (math.inf,math.inf)\n",
    "        crossX=lambda y:(-(b*y+c)/a,y) if a else (math.inf,math.inf)\n",
    "        a,b,c=getAbc(*getCenter(*square1),*getCenter(*square2))\n",
    "        (x1,y1,r1),(x2,y2,r2)=square1,square2\n",
    "        left,right,bottom,top=min(x1,x2),max(x1+r1,x2+r2),min(y1,y2),max(y1+r1,y2+r2)\n",
    "        res=[pt for pt in {crossX(bottom),crossY(left),crossX(top),crossY(right)} if left<=pt[0]<=right and bottom<=pt[1]<=top]\n",
    "        return [v for x,y in sorted(res) for v in [x,y]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cutSquares(self, square1: List[int], square2: List[int]) -> List[float]:\n",
    "        getCenter=lambda x,y,r:[x+r/2,y+r/2]\n",
    "        getAbc=lambda x1,y1,x2,y2:[y2-y1,x1-x2,y1*x2-y2*x1] if [x1,y1]!=[x2,y2] else [1,0,-x1]\n",
    "        crossY=lambda x:(x,-(a*x+c)/b) if b else (math.inf,math.inf)\n",
    "        crossX=lambda y:(-(b*y+c)/a,y) if a else (math.inf,math.inf)\n",
    "        a,b,c=getAbc(*getCenter(*square1),*getCenter(*square2))\n",
    "        (x1,y1,r1),(x2,y2,r2)=square1,square2\n",
    "        left,right,bottom,top=min(x1,x2),max(x1+r1,x2+r2),min(y1,y2),max(y1+r1,y2+r2)\n",
    "        res=[pt for pt in {crossX(bottom),crossY(left),crossX(top),crossY(right)} if left<=pt[0]<=right and bottom<=pt[1]<=top]\n",
    "        return [v for x,y in sorted(res) for v in [x,y]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def cutSquares(self, square1: List[int], square2: List[int]) -> List[float]:\n",
    "        pos_square1 = [square1[0] + square1[2] / 2, square1[1] + square1[2] / 2]\n",
    "        pos_square2 = [square2[0] + square2[2] / 2, square2[1] + square2[2] / 2]\n",
    "        if pos_square1[0] == pos_square2[0]:\n",
    "            return [\n",
    "                pos_square1[0],\n",
    "                min(square1[1], square2[1]),\n",
    "                pos_square2[0],\n",
    "                max(square1[1] + square1[2], square2[1] + square2[2])\n",
    "            ]\n",
    "        else:\n",
    "            k = (pos_square2[1] - pos_square1[1]) / (pos_square2[0] - pos_square1[0])\n",
    "            b = pos_square1[1] - pos_square1[0] * k\n",
    "            res = [0, 0, 0, 0]\n",
    "            if abs(k) > 1:  # 上边与下边相交\n",
    "                res[1] = min(square1[1], square2[1])\n",
    "                res[0] = (res[1] - b) / k\n",
    "                res[3] = max(square1[1] + square1[2], square2[1] + square2[2])\n",
    "                res[2] = (res[3] - b) / k\n",
    "            else:  # 左边与右边相交\n",
    "                res[0] = min(square1[0], square2[0])\n",
    "                res[1] = res[0] * k + b\n",
    "                res[2] = max(square1[0] + square1[2], square2[0] + square2[2])\n",
    "                res[3] = res[2] * k + b\n",
    "            if res[0] > res[2]:\n",
    "                res[0], res[1], res[2], res[3] = res[2], res[3], res[0], res[1]\n",
    "            return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cutSquares(self, square1: List[int], square2: List[int]) -> List[float]:\n",
    "        getCenter=lambda x,y,r: [x+r/2,y+r/2]\n",
    "\n",
    "        getAbc=lambda x1,y1,x2,y2: [y2-y1,x1-x2,y1*x2-y2*x1] if [x1,y1]!=[x2,y2] else [1,0,-x1] #中心重合\n",
    "\n",
    "        crossY=lambda x:(x,-(a*x+c)/b) if b else (math.inf,math.inf)\n",
    "\n",
    "        crossX=lambda y:(-(b*y+c)/a,y) if a else (math.inf,math.inf)\n",
    "\n",
    "        a,b,c=getAbc(*getCenter(*square1),*getCenter(*square2))\n",
    "\n",
    "        (x1,y1,r1),(x2,y2,r2)=square1,square2\n",
    "\n",
    "        left,right,bottom,top=min(x1,x2),max(x1+r1,x2+r2),min(y1,y2),max(y1+r1,y2+r2)\n",
    "\n",
    "        res=[pt for pt in {crossX(bottom),crossY(left),crossX(top),crossY(right)} if left<=pt[0]<=right and bottom<=pt[1]<=top]\n",
    "\n",
    "        return [v for x,y in sorted(res) for v in [x,y]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cutSquares(self, square1: List[int], square2: List[int]) -> List[float]:\n",
    "        x1, y1, d1 = square1\n",
    "        x2, y2 = x1 + d1, y1 + d1\n",
    "        xc1, yc1 = x1 + d1 / 2, y1 + d1 / 2\n",
    "    \n",
    "        x3, y3, d3 = square2\n",
    "        x4, y4 = x3 + d3, y3 + d3\n",
    "        xc2, yc2 = x3 + d3 / 2, y3 + d3 / 2\n",
    "\n",
    "        if xc1 == xc2:\n",
    "            return xc1, min(y1, y3), xc2, max(y2, y4)\n",
    "        elif yc1 == yc2:\n",
    "            return min(x1, x3), yc1, max(x2, x4), yc2\n",
    "        else:\n",
    "            k = (yc2 - yc1) / (xc2 - xc1)\n",
    "            b = yc2 - k * xc2\n",
    "            y1_hat = k * x1 + b\n",
    "            if y1 <= y1_hat <= y2:\n",
    "                y2_hat = k * x2 + b\n",
    "                y3_hat = k * x3 + b\n",
    "                y4_hat = k * x4 + b\n",
    "                points = [(x1, y1_hat), (x2, y2_hat), (x3, y3_hat), (x4, y4_hat)]\n",
    "            else:\n",
    "                x1_hat = (y1 - b) / k\n",
    "                x2_hat = (y2 - b) / k\n",
    "                x3_hat = (y3 - b) / k\n",
    "                x4_hat = (y4 - b) / k\n",
    "                points = [(x1_hat, y1), (x2_hat, y2), (x3_hat, y3), (x4_hat, y4)]\n",
    "        points.sort()\n",
    "        return points[0][0], points[0][1], points[-1][0], points[-1][1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cutSquares(self, square1: List[int], square2: List[int]) -> List[float]:\n",
    "        x1, y1 = square1[0] + square1[2] / 2, square1[1] + square1[2] / 2\n",
    "        x2, y2 = square2[0] + square2[2] / 2, square2[1] + square2[2] / 2\n",
    "        if x1 == x2:\n",
    "            y3 = min(square1[1], square2[1])\n",
    "            y4 = max(square1[1] + square1[2], square2[1] + square2[2])\n",
    "            return [x1, y3, x2, y4]\n",
    "        k = (y2 - y1) / (x2 - x1)\n",
    "        b = y1 - k * x1\n",
    "        if abs(k) > 1:\n",
    "            y3 = min(square1[1], square2[1])\n",
    "            x3 = (y3 - b) / k\n",
    "            y4 = max(square1[1] + square1[2], square2[1] + square2[2])\n",
    "            x4 = (y4 - b) / k\n",
    "            if x3 > x4 or (x3 == x4 and y3 > y4):\n",
    "                x3, y3, x4, y4 = x4, y4, x3, y3\n",
    "        else:\n",
    "            x3 = min(square1[0], square2[0])\n",
    "            y3 = k * x3 + b\n",
    "            x4 = max(square1[0] + square1[2], square2[0] + square2[2])\n",
    "            y4 = k * x4 + b\n",
    "        return [x3, y3, x4, y4]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def cutSquares(self, square1: List[int], square2: List[int]) -> List[float]:\n",
    "        center1 = (square1[0] + square1[2]/2, square1[1] + square1[2]/2)\n",
    "        center2 = (square2[0] + square2[2]/2, square2[1] + square2[2]/2)\n",
    "\n",
    "        def cal_distance(pm, pn):\n",
    "            return math.sqrt((pm[0]-pn[0])**2 + (pm[1]-pn[1])**2), pm, pn\n",
    "\n",
    "        if center1[0] != center2[0]:\n",
    "            k = (center2[1]-center1[1])/(center2[0]-center1[0])\n",
    "            b = center1[1] - k * center1[0]   \n",
    "            if k > 1 or k < -1:\n",
    "                p1 = ((square1[1]-b)/k, square1[1])\n",
    "                p2 = ((square1[1]+square1[2]-b)/k, square1[1]+square1[2])\n",
    "                p3 = ((square2[1]-b)/k, square2[1])\n",
    "                p4 = ((square2[1]+square2[2]-b)/k, square2[1]+square2[2])\n",
    "            else:\n",
    "                p1 = (square1[0], square1[0] * k + b)\n",
    "                p2 = (square1[0] + square1[2], (square1[0] + square1[2]) * k + b) \n",
    "                p3 = (square2[0], square2[0] * k + b)\n",
    "                p4 = (square2[0] + square2[2], (square2[0] + square2[2]) * k + b) \n",
    "            dall = []\n",
    "            dall.append(cal_distance(p1, p2))\n",
    "            dall.append(cal_distance(p1, p3))\n",
    "            dall.append(cal_distance(p1, p4))\n",
    "            dall.append(cal_distance(p2, p3))\n",
    "            dall.append(cal_distance(p2, p4))\n",
    "            dall.append(cal_distance(p3, p4))\n",
    "            dall = sorted(dall, key=lambda x: x[0])\n",
    "            pair = dall[-1]\n",
    "            if pair[1][0] < pair[2][0]:\n",
    "                return pair[1] + pair[2]\n",
    "            else:\n",
    "                return pair[2] + pair[1]\n",
    "        else:  \n",
    "            x = center1[0]\n",
    "            p1 = (x, square1[1])\n",
    "            p2 = (x, square1[1] + square1[2])\n",
    "            p3 = (x, square2[1])\n",
    "            p4 = (x, square2[1] + square2[2])\n",
    "            p  = sorted([p1, p2, p3, p4], key=lambda x: x[1])\n",
    "            return p[0] + p[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cutSquares(self, square1: List[int], square2: List[int]) -> List[float]:\n",
    "        # 计算中心点坐标\n",
    "        circle1 = (square1[0]+square1[2]/2, square1[1]+square1[2]/2)\n",
    "        circle2 = (square2[0]+square2[2]/2, square2[1]+square2[2]/2)\n",
    "        ans = [0]*4\n",
    "        # 判断斜率是否存在\n",
    "        # 中心点x坐标相等，斜率不存在\n",
    "        if circle1[0]==circle2[0]:\n",
    "            ans[0],ans[2] = circle1[0], circle1[0]\n",
    "            ans[1], ans[3] = min(square1[1], square2[1]), max(square1[1]+square1[2], square2[1]+square2[2])\n",
    "            return ans\n",
    "        else:\n",
    "            k = (circle1[1]-circle2[1])/(circle1[0]-circle2[0])\n",
    "            b = circle1[1]-k*circle1[0]\n",
    "            if abs(k)<1: \n",
    "                minx = min(square1[0], square2[0])\n",
    "                maxx = max(square1[0]+square1[2], square2[0]+square2[2])\n",
    "                miny = k*minx+b\n",
    "                maxy = k*maxx+b\n",
    "                return [minx,miny,maxx, maxy]\n",
    "            else:\n",
    "                miny = min(square1[1], square2[1])\n",
    "                maxy = max(square1[1]+square1[2], square2[1]+square2[2])\n",
    "                minx = (miny-b)/k\n",
    "                maxx = (maxy-b)/k\n",
    "                return [minx,miny,maxx, maxy] if minx<maxx else [maxx,maxy,minx,miny]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cutSquares(self, square1: List[int], square2: List[int]) -> List[float]:\n",
    "        xmid1,ymid1 = square1[0]+square1[2]/2,square1[1]+square1[2]/2\n",
    "        xmid2,ymid2 = square2[0]+square2[2]/2,square2[1]+square2[2]/2\n",
    "        tpx = lambda x:[[x[0],x[1],x[1]+x[2]],[x[0]+x[2],x[1],x[1]+x[2]]]\n",
    "        xdots = tpx(square1)+tpx(square2)\n",
    "        xdots.sort(key=lambda x:x[0])\n",
    "        tpy = lambda x:[[x[1],x[0],x[0]+x[2]],[x[1]+x[2],x[0],x[0]+x[2]]]\n",
    "        ydots = tpy(square1)+tpy(square2)\n",
    "        ydots.sort(key=lambda x:x[0])\n",
    "        if xmid2==xmid1:\n",
    "            return [xmid1,ydots[0][0],xmid1,ydots[-1][0]]\n",
    "        xleft,xright = xdots[0],xdots[-1]\n",
    "        yup,ydown = ydots[-1],ydots[0]\n",
    "        k = (ymid2-ymid1)/(xmid2-xmid1)\n",
    "        b = ymid1-k*xmid1\n",
    "        if abs(k)>1:\n",
    "            x1,y1 = (yup[0]-b)/k,yup[0]\n",
    "            x2,y2 = (ydown[0]-b)/k,ydown[0]\n",
    "        else:\n",
    "            x1,y1 = xleft[0],xleft[0]*k+b\n",
    "            x2,y2 = xright[0],xright[0]*k+b\n",
    "\n",
    "        print(x1,x2,y1,y2)\n",
    "        if x1>x2:\n",
    "            x1,x2,y1,y2 = x2,x1,y2,y1\n",
    "        elif x1==x2:\n",
    "            if y1>y2:\n",
    "                y1,y2 = y2,y1\n",
    "        return [x1,y1,x2,y2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class line():\n",
    "    def __init__(self, p1, p2):\n",
    "        self.p1 = p1\n",
    "        self.p2 = p2\n",
    "        self.dx = p2[0] - p1[0]\n",
    "        self.dy = p2[1] - p1[1]\n",
    "        self.k = self.dy/self.dx if self.dx != 0 else math.inf\n",
    "    def get_x(self, y):\n",
    "        return (y-self.p1[1])*self.dx/self.dy + self.p1[0]\n",
    "    def get_y(self, x):\n",
    "        return (x-self.p1[0])*self.dy/self.dx + self.p1[1]\n",
    "\n",
    "class Solution:\n",
    "    def cutSquares(self, square1: List[int], square2: List[int]) -> List[float]:\n",
    "        x1, y1, d1 = square1\n",
    "        x2, y2, d2 = square2\n",
    "        c1 = x1 + d1/2, y1 + d1/2\n",
    "        c2 = x2 + d2/2, y2 + d2/2\n",
    "        cutline = line(c1, c2)\n",
    "        if cutline.k == math.inf:\n",
    "            ys = sorted([y1,y1+d1, y2, y2+d2])\n",
    "            return c1[0], ys[0], c2[0], ys[-1]\n",
    "        else:\n",
    "            if abs(cutline.k) > 1:\n",
    "                yb1 = min(y1,y2)\n",
    "                yb2 = max(y1+d1, y2+d2)\n",
    "                if cutline.k < 0:\n",
    "                    yb1, yb2 = yb2, yb1\n",
    "                xb1 = cutline.get_x(yb1)\n",
    "                xb2 = cutline.get_x(yb2)\n",
    "            else:\n",
    "                xb1 = min(x1,x2)\n",
    "                xb2 = max(x1+d1, x2+d2)\n",
    "                yb1 = cutline.get_y(xb1)\n",
    "                yb2 = cutline.get_y(xb2)\n",
    "            return xb1, yb1, xb2, yb2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def cutSquares(self, square1: List[int], square2: List[int]) -> List[float]:\n",
    "        center1 = (square1[0] + square1[2]/2, square1[1] + square1[2]/2)\n",
    "        center2 = (square2[0] + square2[2]/2, square2[1] + square2[2]/2)\n",
    "\n",
    "        def cal_distance(pm, pn):\n",
    "            return math.sqrt((pm[0]-pn[0])**2 + (pm[1]-pn[1])**2), pm, pn\n",
    "\n",
    "        if center1[0] != center2[0]:\n",
    "            k = (center2[1]-center1[1])/(center2[0]-center1[0])\n",
    "            b = center1[1] - k * center1[0]   \n",
    "            if k > 1 or k < -1:\n",
    "                p1 = ((square1[1]-b)/k, square1[1])\n",
    "                p2 = ((square1[1]+square1[2]-b)/k, square1[1]+square1[2])\n",
    "                p3 = ((square2[1]-b)/k, square2[1])\n",
    "                p4 = ((square2[1]+square2[2]-b)/k, square2[1]+square2[2])\n",
    "            else:\n",
    "                p1 = (square1[0], square1[0] * k + b)\n",
    "                p2 = (square1[0] + square1[2], (square1[0] + square1[2]) * k + b) \n",
    "                p3 = (square2[0], square2[0] * k + b)\n",
    "                p4 = (square2[0] + square2[2], (square2[0] + square2[2]) * k + b) \n",
    "            dall = []\n",
    "            dall.append(cal_distance(p1, p2))\n",
    "            dall.append(cal_distance(p1, p3))\n",
    "            dall.append(cal_distance(p1, p4))\n",
    "            dall.append(cal_distance(p2, p3))\n",
    "            dall.append(cal_distance(p2, p4))\n",
    "            dall.append(cal_distance(p3, p4))\n",
    "            dall = sorted(dall, key=lambda x: x[0])\n",
    "            pair = dall[-1]\n",
    "            if pair[1][0] < pair[2][0]:\n",
    "                return pair[1] + pair[2]\n",
    "            else:\n",
    "                return pair[2] + pair[1]\n",
    "        else:  \n",
    "            x = center1[0]\n",
    "            p1 = (x, square1[1])\n",
    "            p2 = (x, square1[1] + square1[2])\n",
    "            p3 = (x, square2[1])\n",
    "            p4 = (x, square2[1] + square2[2])\n",
    "            p  = sorted([p1, p2, p3, p4], key=lambda x: x[1])\n",
    "            return p[0] + p[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def cutSquares(self, square1: List[int], square2: List[int]) -> List[float]:\n",
    "        center1 = (square1[0] + square1[2]/2, square1[1] + square1[2]/2)\n",
    "        center2 = (square2[0] + square2[2]/2, square2[1] + square2[2]/2)\n",
    "\n",
    "        def cal_distance(pm, pn):\n",
    "            return math.sqrt((pm[0]-pn[0])**2 + (pm[1]-pn[1])**2), pm, pn\n",
    "\n",
    "        if center1[0] != center2[0]:\n",
    "            k = (center2[1]-center1[1])/(center2[0]-center1[0])\n",
    "            b = center1[1] - k * center1[0]   \n",
    "            if k > 1 or k < -1:\n",
    "                p1 = ((square1[1]-b)/k, square1[1])\n",
    "                p2 = ((square1[1]+square1[2]-b)/k, square1[1]+square1[2])\n",
    "                p3 = ((square2[1]-b)/k, square2[1])\n",
    "                p4 = ((square2[1]+square2[2]-b)/k, square2[1]+square2[2])\n",
    "            else:\n",
    "                p1 = (square1[0], square1[0] * k + b)\n",
    "                p2 = (square1[0] + square1[2], (square1[0] + square1[2]) * k + b) \n",
    "                p3 = (square2[0], square2[0] * k + b)\n",
    "                p4 = (square2[0] + square2[2], (square2[0] + square2[2]) * k + b) \n",
    "            dall = []\n",
    "            dall.append(cal_distance(p1, p2))\n",
    "            dall.append(cal_distance(p1, p3))\n",
    "            dall.append(cal_distance(p1, p4))\n",
    "            dall.append(cal_distance(p2, p3))\n",
    "            dall.append(cal_distance(p2, p4))\n",
    "            dall.append(cal_distance(p3, p4))\n",
    "            dall = sorted(dall, key=lambda x: x[0])\n",
    "            pair = dall[-1]\n",
    "            if pair[1][0] < pair[2][0]:\n",
    "                return pair[1] + pair[2]\n",
    "            else:\n",
    "                return pair[2] + pair[1]\n",
    "        else:  \n",
    "            x = center1[0]\n",
    "            p1 = (x, square1[1])\n",
    "            p2 = (x, square1[1] + square1[2])\n",
    "            p3 = (x, square2[1])\n",
    "            p4 = (x, square2[1] + square2[2])\n",
    "            p  = sorted([p1, p2, p3, p4], key=lambda x: x[1])\n",
    "            return p[0] + p[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cutSquares(self, square1: List[int], square2: List[int]) -> List[float]:\n",
    "        center1 = [square1[0]+square1[2]/2, square1[1]+square1[2]/2]\n",
    "        center2 = [square2[0]+square2[2]/2, square2[1]+square2[2]/2]\n",
    "        if center1[0] == center2[0]:\n",
    "            y1 = min(square1[1], square2[1])\n",
    "            y2 = max(square1[1]+square1[2], square2[1]+square2[2])\n",
    "            return [center1[0], y1, center1[0], y2]\n",
    "        if center1[1] == center2[1]:\n",
    "            x1 = min(square1[0], square2[0])\n",
    "            x2 = max(square1[0]+square1[2], square2[0]+square2[2])\n",
    "            return [x1, center1[1], x2, center1[1]]\n",
    "        k = (center1[1]-center2[1])/(center1[0]-center2[0])\n",
    "        if abs(k) <= 1:\n",
    "            x1 = min(square1[0], square2[0])\n",
    "            x2 = max(square1[0]+square1[2], square2[0]+square2[2])\n",
    "            y1 = k*(x1-center1[0])+center1[1]\n",
    "            y2 = k*(x2-center1[0])+center1[1]\n",
    "        else:\n",
    "            y1 = min(square1[1], square2[1])\n",
    "            y2 = max(square1[1]+square1[2], square2[1]+square2[2])\n",
    "            x1 = 1/k*(y1-center1[1])+center1[0]\n",
    "            x2 = 1/k*(y2-center1[1])+center1[0]\n",
    "        return [x1, y1, x2, y2] if x1 < x2 else [x2, y2, x1, y1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cutSquares(self, square1: List[int], square2: List[int]) -> List[float]:\n",
    "        x1, y1, z1 = square1\n",
    "        x2, y2, z2 = square2\n",
    "        cx12 = x1 * 2 + z1\n",
    "        cy12 = y1 * 2 + z1\n",
    "        cx22 = x2 * 2 + z2\n",
    "        cy22 = y2 * 2 + z2\n",
    "        if cx12 == cx22:\n",
    "            y = [y1, y1 + z1, y2, y2 + z2]\n",
    "            return [cx12 / 2.0, float(min(y)), cx12 / 2.0, float(max(y))]\n",
    "        if cy12 == cy22:\n",
    "            x = [x1, x1 + z1, x2, x2 + z2]\n",
    "            return [float(min(x)), cy12 / 2.0, float(max(x)), cy12 / 2.0]\n",
    "        if cy22 - cy12 == cx22 - cx12:  # k=1\n",
    "            p = [(x1, y1), (x1 + z1, y1 + z1), (x2, y2), (x2 + z2, y2 + z2)]\n",
    "        elif cy22 - cy12 == cx12 - cx22:  # k=-1\n",
    "            p = [(x1 + z1, y1), (x1, y1 + z1), (x2 + z2, y2), (x2, y2 + z2)]\n",
    "        else:\n",
    "            cx1, cy1 = cx12 / 2.0, cy12 / 2.0\n",
    "            cx2, cy2 = cx22 / 2.0, cy22 / 2.0\n",
    "            k = (cy2 - cy1) / (cx2 - cx1)\n",
    "            b = cy1 - k * cx1\n",
    "            if abs(k) < 1.0:\n",
    "                p = [\n",
    "                    (x1, k * x1 + b),\n",
    "                    (x1 + z1, k * (x1 + z1) + b),\n",
    "                    (x2, k * x2 + b),\n",
    "                    (x2 + z2, k * (x2 + z2) + b),\n",
    "                ]\n",
    "            else:\n",
    "                p = [\n",
    "                    ((y1 - b) / k, y1),\n",
    "                    ((y1 + z1 - b) / k, y1 + z1),\n",
    "                    ((y2 - b) / k, y2),\n",
    "                    ((y2 + z2 - b) / k, y2 + z2),\n",
    "                ]\n",
    "        p.sort()\n",
    "        return [float(p[0][0]), float(p[0][1]), float(p[-1][0]), float(p[-1][1])]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cutSquares(self, square1: List[int], square2: List[int]) -> List[float]:\n",
    "        x1, y1 = square1[0] + square1[2] / 2, square1[1] + square1[2] / 2\n",
    "        x2, y2 = square2[0] + square2[2] / 2, square2[1] + square2[2] / 2\n",
    "        if x1 == x2:\n",
    "            y3 = min(square1[1], square2[1])\n",
    "            y4 = max(square1[1] + square1[2], square2[1] + square2[2])\n",
    "            return [x1, y3, x2, y4]\n",
    "        k = (y2 - y1) / (x2 - x1)\n",
    "        b = y1 - k * x1\n",
    "        if abs(k) > 1:\n",
    "            y3 = min(square1[1], square2[1])\n",
    "            x3 = (y3 - b) / k\n",
    "            y4 = max(square1[1] + square1[2], square2[1] + square2[2])\n",
    "            x4 = (y4 - b) / k\n",
    "            if x3 > x4 or (x3 == x4 and y3 > y4):\n",
    "                x3, y3, x4, y4 = x4, y4, x3, y3\n",
    "        else:\n",
    "            x3 = min(square1[0], square2[0])\n",
    "            y3 = k * x3 + b\n",
    "            x4 = max(square1[0] + square1[2], square2[0] + square2[2])\n",
    "            y4 = k * x4 + b\n",
    "        return [x3, y3, x4, y4]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def cutSquares(self, square1: List[int], square2: List[int]) -> List[float]:\n",
    "#         #要平分两个正方形，则平分线一定是两个正方形中点的连线\n",
    "#         #1.计算两个正方形的中心坐标 2.判断此时两点形成的直线斜率是否存在 \n",
    "#         #3.若不存在则说明两点在同一条x轴上\n",
    "#         #若存在，则计算斜率k和系数b 5.根据斜率的绝对值的大小，\n",
    "#         #可以知道直线与正方形的上下相交还是左右相交\n",
    "#         cx1 = square1[0] + square1[2] / 2\n",
    "#         cy1 = square1[1] + square1[2] / 2\n",
    "        \n",
    "#         cx2 = square2[0] + square2[2] / 2\n",
    "#         cy2 = square2[1] + square2[2] / 2\n",
    "\n",
    "#         res = []\n",
    "#         #两点式子\n",
    "#         if cx1 == cx2: #垂直\n",
    "#             res.append(cx1,square1[1])\n",
    "#             res.append(cx1,square2[1])\n",
    "#             res.append(cx1,square1[1]+square1[2])\n",
    "#             res.append(cx1,square1[1]+square2[2])\n",
    "#         elif cy1 == cy2: #平行\n",
    "#             res.append(square1[0],cy1)\n",
    "#             res.append(square2[0],cy1)\n",
    "#             res.append(square1[0]+square1[2],cy1)\n",
    "#             res.append(square2[0]+square2[2],cy1)\n",
    "#         else:\n",
    "#             k = ()\n",
    "class Solution:\n",
    "    def cutSquares(self, square1: List[int], square2: List[int]) -> List[float]:\n",
    "        get_x = lambda y: (y - b) / k\n",
    "        get_y = lambda x: k * x + b\n",
    "        \n",
    "        (x1, y1, l1), (x2, y2, l2) = square1, square2\n",
    "        c1 = (x1 + l1 / 2, y1 + l1 / 2)\n",
    "        c2 = (x2 + l2 / 2, y2 + l2 / 2)\n",
    "        dy, dx = c2[1] - c1[1], c2[0] - c1[0]\n",
    "        points = []\n",
    "        if dx == 0:\n",
    "            points = [(c1[0], y1), (c1[0], y1 + l1), (c1[0], y2), (c1[0], y2 + l2)]\n",
    "        else:\n",
    "            k = dy / dx\n",
    "            b = c1[1] - c1[0] * k\n",
    "            if -1 <= k <= 1:\n",
    "                points = [(x1, get_y(x1)), (x1 + l1, get_y(x1 + l1)), \n",
    "                          (x2, get_y(x2)), (x2 + l2, get_y(x2 + l2))]\n",
    "            else:\n",
    "                points = [(get_x(y1), y1), (get_x(y1 + l1), y1 + l1),\n",
    "                          (get_x(y2), y2), (get_x(y2 + l2), y2 + l2)]\n",
    "        points = sorted(points)\n",
    "        return [*points[0], *points[-1]]\n",
    "            \n",
    "\n",
    "# class Solution:\n",
    "#     def cutSquares(self, square1: List[int], square2: List[int]) -> List[float]:\n",
    "#         getCenter=lambda x,y,r: [x+r/2,y+r/2]\n",
    "#         getAbc=lambda x1,y1,x2,y2: [y2-y1,x1-x2,y1*x2-y2*x1] if [x1,y1]!=[x2,y2] else [1,0,-x1] #中心重合\n",
    "#         crossY=lambda x:(x,-(a*x+c)/b) if b else (math.inf,math.inf)\n",
    "#         crossX=lambda y:(-(b*y+c)/a,y) if a else (math.inf,math.inf)\n",
    "#         a,b,c=getAbc(*getCenter(*square1),*getCenter(*square2))\n",
    "#         (x1,y1,r1),(x2,y2,r2)=square1,square2\n",
    "#         left,right,bottom,top=min(x1,x2),max(x1+r1,x2+r2),min(y1,y2),max(y1+r1,y2+r2)\n",
    "#         res=[pt for pt in {crossX(bottom),crossY(left),crossX(top),crossY(right)} if left<=pt[0]<=right and bottom<=pt[1]<=top]\n",
    "#         return [v for x,y in sorted(res) for v in [x,y]]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cutSquares(self, square1: List[int], square2: List[int]) -> List[float]:\n",
    "        xmid1,ymid1 = square1[0]+square1[2]/2,square1[1]+square1[2]/2\n",
    "        xmid2,ymid2 = square2[0]+square2[2]/2,square2[1]+square2[2]/2\n",
    "        tpx = lambda x:[[x[0],x[1],x[1]+x[2]],[x[0]+x[2],x[1],x[1]+x[2]]]\n",
    "        xdots = tpx(square1)+tpx(square2)\n",
    "        xdots.sort(key=lambda x:x[0])\n",
    "        tpy = lambda x:[[x[1],x[0],x[0]+x[2]],[x[1]+x[2],x[0],x[0]+x[2]]]\n",
    "        ydots = tpy(square1)+tpy(square2)\n",
    "        ydots.sort(key=lambda x:x[0])\n",
    "        if xmid2==xmid1:\n",
    "            return [xmid1,ydots[0][0],xmid1,ydots[-1][0]]\n",
    "        xleft,xright = xdots[0],xdots[-1]\n",
    "        yup,ydown = ydots[-1],ydots[0]\n",
    "        k = (ymid2-ymid1)/(xmid2-xmid1)\n",
    "        b = ymid1-k*xmid1\n",
    "        if abs(k)>1:\n",
    "            x1,y1 = (yup[0]-b)/k,yup[0]\n",
    "            x2,y2 = (ydown[0]-b)/k,ydown[0]\n",
    "        else:\n",
    "            x1,y1 = xleft[0],xleft[0]*k+b\n",
    "            x2,y2 = xright[0],xright[0]*k+b\n",
    "        if x1>x2:\n",
    "            x1,x2,y1,y2 = x2,x1,y2,y1\n",
    "        elif x1==x2:\n",
    "            if y1>y2:\n",
    "                y1,y2 = y2,y1\n",
    "        return [x1,y1,x2,y2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def cutSquares(self, square1: List[int], square2: List[int]) -> List[float]:\n",
    "        center1 = (square1[0] + square1[2]/2, square1[1] + square1[2]/2)\n",
    "        center2 = (square2[0] + square2[2]/2, square2[1] + square2[2]/2)\n",
    "\n",
    "        def cal_distance(pm, pn):\n",
    "            return math.sqrt((pm[0]-pn[0])**2 + (pm[1]-pn[1])**2), pm, pn\n",
    "\n",
    "        if center1[0] != center2[0]:\n",
    "            k = (center2[1]-center1[1])/(center2[0]-center1[0])\n",
    "            b = center1[1] - k * center1[0]   \n",
    "            if k > 1 or k < -1:\n",
    "                p1 = ((square1[1]-b)/k, square1[1])\n",
    "                p2 = ((square1[1]+square1[2]-b)/k, square1[1]+square1[2])\n",
    "                p3 = ((square2[1]-b)/k, square2[1])\n",
    "                p4 = ((square2[1]+square2[2]-b)/k, square2[1]+square2[2])\n",
    "            else:\n",
    "                p1 = (square1[0], square1[0] * k + b)\n",
    "                p2 = (square1[0] + square1[2], (square1[0] + square1[2]) * k + b) \n",
    "                p3 = (square2[0], square2[0] * k + b)\n",
    "                p4 = (square2[0] + square2[2], (square2[0] + square2[2]) * k + b) \n",
    "            dall = []\n",
    "            dall.append(cal_distance(p1, p2))\n",
    "            dall.append(cal_distance(p1, p3))\n",
    "            dall.append(cal_distance(p1, p4))\n",
    "            dall.append(cal_distance(p2, p3))\n",
    "            dall.append(cal_distance(p2, p4))\n",
    "            dall.append(cal_distance(p3, p4))\n",
    "            dall = sorted(dall, key=lambda x: x[0])\n",
    "            pair = dall[-1]\n",
    "            if pair[1][0] < pair[2][0]:\n",
    "                return pair[1] + pair[2]\n",
    "            else:\n",
    "                return pair[2] + pair[1]\n",
    "        else:  \n",
    "            x = center1[0]\n",
    "            p1 = (x, square1[1])\n",
    "            p2 = (x, square1[1] + square1[2])\n",
    "            p3 = (x, square2[1])\n",
    "            p4 = (x, square2[1] + square2[2])\n",
    "            p  = sorted([p1, p2, p3, p4], key=lambda x: x[1])\n",
    "            return p[0] + p[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cutSquares(self, square1: List[int], square2: List[int]) -> List[float]:\n",
    "        get_x = lambda y: (y - b) / k\n",
    "        get_y = lambda x: k * x + b\n",
    "        \n",
    "        (x1, y1, l1), (x2, y2, l2) = square1, square2\n",
    "        c1 = (x1 + l1 / 2, y1 + l1 / 2)\n",
    "        c2 = (x2 + l2 / 2, y2 + l2 / 2)\n",
    "        dy, dx = c2[1] - c1[1], c2[0] - c1[0]\n",
    "        points = []\n",
    "        if dx == 0:\n",
    "            points = [(c1[0], y1), (c1[0], y1 + l1), (c1[0], y2), (c1[0], y2 + l2)]\n",
    "        else:\n",
    "            k = dy / dx\n",
    "            b = c1[1] - c1[0] * k\n",
    "            if -1 <= k <= 1:\n",
    "                points = [(x1, get_y(x1)), (x1 + l1, get_y(x1 + l1)), \n",
    "                          (x2, get_y(x2)), (x2 + l2, get_y(x2 + l2))]\n",
    "            else:\n",
    "                points = [(get_x(y1), y1), (get_x(y1 + l1), y1 + l1),\n",
    "                          (get_x(y2), y2), (get_x(y2 + l2), y2 + l2)]\n",
    "        points = sorted(points)\n",
    "        return [*points[0], *points[-1]]\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cutSquares(self, square1: List[int], square2: List[int]) -> List[float]:\n",
    "        x1 = square1[0] + square1[2] / 2\n",
    "        y1 = square1[1] + square1[2] / 2\n",
    "        x2 = square2[0] + square2[2] / 2\n",
    "        y2 = square2[1] + square2[2] / 2\n",
    "        res = [0, 0, 0, 0]\n",
    "        if x1 == x2:\n",
    "            res[0] = x1\n",
    "            res[1] = min(square1[1], square2[1])\n",
    "            res[2] = x1\n",
    "            res[3] = max(square1[1]+square1[2], square2[1]+square2[2])\n",
    "        else:\n",
    "            k = (y1-y2) / (x1-x2)\n",
    "            b = y1 - k*x1\n",
    "            if abs(k) > 1:\n",
    "                res[1] = min(square1[1], square2[1])\n",
    "                res[0] = (res[1]-b) / k\n",
    "                res[3] = max(square1[1]+square1[2], square2[1]+square2[2])\n",
    "                res[2] = (res[3]-b) / k\n",
    "            else:\n",
    "                res[0] = min(square1[0], square2[0])\n",
    "                res[1] = res[0]*k + b\n",
    "                res[2] = max(square1[0]+square1[2], square2[0]+square2[2])\n",
    "                res[3] = res[2]*k + b\n",
    "\n",
    "            if res[0] > res[2]:\n",
    "                res[0], res[2] = res[2], res[0]\n",
    "                res[1], res[3] = res[3], res[1]\n",
    "\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cutSquares(self, square1: List[int], square2: List[int]) -> List[float]:\n",
    "        get_x = lambda y: (y - b) / k\n",
    "        get_y = lambda x: k * x + b\n",
    "        \n",
    "        (x1, y1, l1), (x2, y2, l2) = square1, square2\n",
    "        c1 = (x1 + l1 / 2, y1 + l1 / 2)\n",
    "        c2 = (x2 + l2 / 2, y2 + l2 / 2)\n",
    "        dy, dx = c2[1] - c1[1], c2[0] - c1[0]\n",
    "        points = []\n",
    "        if dx == 0:\n",
    "            points = [(c1[0], y1), (c1[0], y1 + l1), (c1[0], y2), (c1[0], y2 + l2)]\n",
    "        else:\n",
    "            k = dy / dx\n",
    "            b = c1[1] - c1[0] * k\n",
    "            if -1 <= k <= 1:\n",
    "                points = [(x1, get_y(x1)), (x1 + l1, get_y(x1 + l1)), \n",
    "                          (x2, get_y(x2)), (x2 + l2, get_y(x2 + l2))]\n",
    "            else:\n",
    "                points = [(get_x(y1), y1), (get_x(y1 + l1), y1 + l1),\n",
    "                          (get_x(y2), y2), (get_x(y2 + l2), y2 + l2)]\n",
    "        points = sorted(points)\n",
    "        return [*points[0], *points[-1]]\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cutSquares(self, square1: List[int], square2: List[int]) -> List[float]:\n",
    "        xmid1,ymid1 = square1[0]+square1[2]/2,square1[1]+square1[2]/2\n",
    "        xmid2,ymid2 = square2[0]+square2[2]/2,square2[1]+square2[2]/2\n",
    "        tpx = lambda x:[[x[0],x[1],x[1]+x[2]],[x[0]+x[2],x[1],x[1]+x[2]]]\n",
    "        xdots = tpx(square1)+tpx(square2)\n",
    "        xdots.sort(key=lambda x:x[0])\n",
    "        tpy = lambda x:[[x[1],x[0],x[0]+x[2]],[x[1]+x[2],x[0],x[0]+x[2]]]\n",
    "        ydots = tpy(square1)+tpy(square2)\n",
    "        ydots.sort(key=lambda x:x[0])\n",
    "        if xmid2==xmid1:\n",
    "            return [xmid1,ydots[0][0],xmid1,ydots[-1][0]]\n",
    "        xleft,xright = xdots[0],xdots[-1]\n",
    "        yup,ydown = ydots[-1],ydots[0]\n",
    "        k = (ymid2-ymid1)/(xmid2-xmid1)\n",
    "        b = ymid1-k*xmid1\n",
    "        if abs(k)>1:\n",
    "            x1,y1 = (yup[0]-b)/k,yup[0]\n",
    "            x2,y2 = (ydown[0]-b)/k,ydown[0]\n",
    "        else:\n",
    "            x1,y1 = xleft[0],xleft[0]*k+b\n",
    "            x2,y2 = xright[0],xright[0]*k+b\n",
    "        if x1>x2:\n",
    "            x1,x2,y1,y2 = x2,x1,y2,y1\n",
    "        elif x1==x2:\n",
    "            if y1>y2:\n",
    "                y1,y2 = y2,y1\n",
    "        return [x1,y1,x2,y2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef cutSquares(self, square1, square2):\n",
    "\t\tr1 = square1[2] / 2\n",
    "\t\tr2 = square2[2] / 2\n",
    "\t\tc1 = [square1[0] + r1, square1[1] + r1]\n",
    "\t\tc2 = [square2[0] + r2, square2[1] + r2]\n",
    "\t\tif c1[0] == c2[0] or c1 == c2:\n",
    "\t\t\treturn [c1[0], min(c1[1] - r1, c2[1] - r2), c1[0], max(c1[1] + r1, c2[1] + r2)]\n",
    "\t\tif c1[1] == c2[1]:\n",
    "\t\t\treturn [min(c1[0] - r1, c2[0] - r2), c1[1], max(c1[0] + r1, c2[0] + r2), c1[1]]\n",
    "\t\tk = (c2[1] - c1[1]) / (c2[0] - c1[0])\n",
    "\t\tb = c1[1] - k * c1[0]\n",
    "\t\tif abs(k) >= 1:\n",
    "\t\t\tlowy = min(square1[1], square2[1])\n",
    "\t\t\thighy = max(square1[1] + square1[2], square2[1] + square2[2])\n",
    "\t\t\tans = [(lowy - b) / k, lowy, (highy - b) / k, highy]\n",
    "\t\telse:\n",
    "\t\t\tlowx = min(square1[0], square2[0])\n",
    "\t\t\thighx = max(square1[0] + square1[2], square2[0] + square2[2])\n",
    "\t\t\tans = [lowx, k * lowx + b, highx, k * highx + b]\n",
    "\t\tif ans[0] < ans[2] or (ans[0] == ans[2] and ans[1] <= ans[3]):\n",
    "\t\t\treturn ans\n",
    "\t\treturn ans[2:] + ans[:2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cutSquares(self, square1: List[int], square2: List[int]) -> List[float]:\n",
    "        get_x = lambda y: (y - b) / k\n",
    "        get_y = lambda x: k * x + b\n",
    "        \n",
    "        (x1, y1, l1), (x2, y2, l2) = square1, square2\n",
    "        c1 = (x1 + l1 / 2, y1 + l1 / 2)\n",
    "        c2 = (x2 + l2 / 2, y2 + l2 / 2)\n",
    "        dy, dx = c2[1] - c1[1], c2[0] - c1[0]\n",
    "        points = []\n",
    "        if dx == 0:\n",
    "            points = [(c1[0], y1), (c1[0], y1 + l1), (c1[0], y2), (c1[0], y2 + l2)]\n",
    "        else:\n",
    "            k = dy / dx\n",
    "            b = c1[1] - c1[0] * k\n",
    "            if -1 <= k <= 1:\n",
    "                points = [(x1, get_y(x1)), (x1 + l1, get_y(x1 + l1)), \n",
    "                          (x2, get_y(x2)), (x2 + l2, get_y(x2 + l2))]\n",
    "            else:\n",
    "                points = [(get_x(y1), y1), (get_x(y1 + l1), y1 + l1),\n",
    "                          (get_x(y2), y2), (get_x(y2 + l2), y2 + l2)]\n",
    "        points = sorted(points)\n",
    "        return [*points[0], *points[-1]]\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cutSquares(self, square1: List[int], square2: List[int]) -> List[float]:\n",
    "        if square1[0] > square2[0]:\n",
    "            return self.cutSquares(square2, square1)\n",
    "        l1, l2 = square1[2], square2[2]\n",
    "        x1, y1 = square1[0] + l1/2, square1[1] + l1/2\n",
    "        x2, y2 = square2[0] + l2/2, square2[1] + l2/2\n",
    "        if x1 == x2 or (x1, y1) == (x2, y2):\n",
    "            return [x1, min(square1[1], square2[1]), x2, max(square2[1]+l2, square1[1]+l1)]\n",
    "        k = (y1-y2)/(x1-x2)\n",
    "        b = y1 - k*x1\n",
    "        if k > 1:\n",
    "            y1 = min(square1[1], square2[1])\n",
    "            x1 = (y1-b)/k\n",
    "            y2 = max(square1[1] + l1, square2[1] + l2)\n",
    "            x2 = (y2-b)/k\n",
    "        elif k < -1:\n",
    "            y1 = max(square1[1] + l1, square2[1] + l2)\n",
    "            x1 = (y1-b)/k\n",
    "            y2 = min(square1[1], square2[1])\n",
    "            x2 = (y2-b)/k\n",
    "        else:\n",
    "            x1 = square1[0]\n",
    "            y1 = k*x1 + b\n",
    "            x2 = max(square1[0] + l1, square2[0] + l2)\n",
    "            y2 = k*x2 + b\n",
    "        return [x1, y1, x2, y2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cutSquares(self, square1: List[int], square2: List[int]) -> List[float]:\n",
    "        getCenter=lambda x,y,r: [x+r/2,y+r/2]\n",
    "        getAbc=lambda x1,y1,x2,y2: [y2-y1,x1-x2,y1*x2-y2*x1] if [x1,y1]!=[x2,y2] else [1,0,-x1] #中心重合\n",
    "        crossY=lambda x:(x,-(a*x+c)/b) if b else (math.inf,math.inf)\n",
    "        crossX=lambda y:(-(b*y+c)/a,y) if a else (math.inf,math.inf)\n",
    "        a,b,c=getAbc(*getCenter(*square1),*getCenter(*square2))\n",
    "        (x1,y1,r1),(x2,y2,r2)=square1,square2\n",
    "        left,right,bottom,top=min(x1,x2),max(x1+r1,x2+r2),min(y1,y2),max(y1+r1,y2+r2)\n",
    "        res=[pt for pt in {crossX(bottom),crossY(left),crossX(top),crossY(right)} if left<=pt[0]<=right and bottom<=pt[1]<=top]\n",
    "        return [v for x,y in sorted(res) for v in [x,y]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cutSquares(self, square1: List[int], square2: List[int]) -> List[float]:\n",
    "        x1, y1, d1 = square1\n",
    "        x2, y2 = x1 + d1, y1 + d1\n",
    "        xc1, yc1 = x1 + d1/2, y1 + d1/2\n",
    "\n",
    "        x3, y3, d3 = square2\n",
    "        x4, y4 = x3 + d3, y3 + d3\n",
    "        xc2, yc2 = x3 + d3/2, y3 + d3/2\n",
    "\n",
    "        if xc1==xc2: \n",
    "            return xc1,min(y1,y3),xc1,max(y2,y4)\n",
    "        if yc1==yc2:\n",
    "            return min(x1,x3),yc1,max(x2,x4),yc2\n",
    "        k=(yc2-yc1)/(xc2-xc1)\n",
    "        b=yc2-k*xc2\n",
    "        y1_hat=k*x1+b\n",
    "        if y1<=y1_hat<=y2:#左右\n",
    "            y2_hat=k*x2+b\n",
    "            y3_hat=k*x3+b\n",
    "            y4_hat=k*x4+b\n",
    "            points=[(x1,y1_hat),(x2,y2_hat),(x3,y3_hat),(x4,y4_hat)]\n",
    "            points.sort()\n",
    "            return points[0][0],points[0][1],points[-1][0],points[-1][1]\n",
    "        #上下\n",
    "        x1_hat=(y1-b)/k\n",
    "        x2_hat=(y2-b)/k\n",
    "        x3_hat=(y3-b)/k\n",
    "        x4_hat=(y4-b)/k\n",
    "        points=[(x1_hat,y1),(x2_hat,y2),(x3_hat,y3),(x4_hat,y4)]\n",
    "        points.sort()\n",
    "        return points[0][0],points[0][1],points[-1][0],points[-1][1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cutSquares(self, square1: List[int], square2: List[int]) -> List[float]:\n",
    "        # 要平分两个正方形，则平分线一定是两个正方形中点的连线\n",
    "        get_x = lambda y: (y - b) / k\n",
    "        get_y = lambda x: k * x + b\n",
    "        \n",
    "        (x1, y1, l1), (x2, y2, l2) = square1, square2\n",
    "        c1 = (x1 + l1 / 2, y1 + l1 / 2) # 计算两个正方形的中心坐标\n",
    "        c2 = (x2 + l2 / 2, y2 + l2 / 2)\n",
    "        dy, dx = c2[1] - c1[1], c2[0] - c1[0]\n",
    "        points = []\n",
    "        if dx == 0: # 两个中心坐标在同一条x轴上，此时两条直线的斜率都是无穷大\n",
    "            points = [(c1[0], y1), (c1[0], y1 + l1), (c1[0], y2), (c1[0], y2 + l2)]\n",
    "        else: # 斜率存在，则计算斜率和系数，y = kx + b\n",
    "            k = dy / dx\n",
    "            b = c1[1] - c1[0] * k\n",
    "            if -1 <= k <= 1: # 斜率绝对值小于等于1，左右相交\n",
    "                points = [(x1, get_y(x1)), (x1 + l1, get_y(x1 + l1)), \n",
    "                          (x2, get_y(x2)), (x2 + l2, get_y(x2 + l2))]\n",
    "            else: # 斜率绝对值大于1，上下相交\n",
    "                points = [(get_x(y1), y1), (get_x(y1 + l1), y1 + l1),\n",
    "                          (get_x(y2), y2), (get_x(y2 + l2), y2 + l2)]\n",
    "        points = sorted(points)\n",
    "        return [*points[0], *points[-1]]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cutSquares(self, square1: List[int], square2: List[int]) -> List[float]:\n",
    "        get_x = lambda y: (y - b) / k\n",
    "        get_y = lambda x: k * x + b\n",
    "        \n",
    "        (x1, y1, l1), (x2, y2, l2) = square1, square2\n",
    "        c1 = (x1 + l1 / 2, y1 + l1 / 2)\n",
    "        c2 = (x2 + l2 / 2, y2 + l2 / 2)\n",
    "        dy, dx = c2[1] - c1[1], c2[0] - c1[0]\n",
    "        points = []\n",
    "        if dx == 0:\n",
    "            points = [(c1[0], y1), (c1[0], y1 + l1), (c1[0], y2), (c1[0], y2 + l2)]\n",
    "        else:\n",
    "            k = dy / dx\n",
    "            b = c1[1] - c1[0] * k\n",
    "            if -1 <= k <= 1:\n",
    "                points = [(x1, get_y(x1)), (x1 + l1, get_y(x1 + l1)), \n",
    "                          (x2, get_y(x2)), (x2 + l2, get_y(x2 + l2))]\n",
    "            else:\n",
    "                points = [(get_x(y1), y1), (get_x(y1 + l1), y1 + l1),\n",
    "                          (get_x(y2), y2), (get_x(y2 + l2), y2 + l2)]\n",
    "        points = sorted(points)\n",
    "        return [*points[0], *points[-1]]\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
